//3370. 仅含置位位的最小整数

//给你一个正整数 n。
//返回 大于等于 n 且二进制表示仅包含 置位 位的 最小 整数 x 。
//置位 位指的是二进制表示中值为 1 的位。

//class Solution {
//public:
//    int smallestNumber(int n) {
//        return (1 << (int)log2(n) + 1) - 1;//bit_width((uint32_t) n) = (int)log2(n) + 1
//    }
//};

//3226. 使两个整数相等的位更改次数

//给你两个正整数 n 和 k。
//你可以选择 n 的 二进制表示 中任意一个值为 1 的位，并将其改为 0。
//返回使得 n 等于 k 所需要的更改次数。如果无法实现，返回 - 1。

//class Solution {
//public:
//    int minChanges(int n, int k) {
//        return (n & k) != k ? -1 : popcount(static_cast<uint32_t>(n ^ k));
//    }
//};

//1356. 根据数字二进制下 1 的数目排序

//给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
//如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
//请你返回排序后的数组。

//int bit[10001]{};
//int init = [] {
//    for (int i = 1; i <= 10000; ++i) {
//        bit[i] = bit[i >> 1] + (i & 1);
//    }
//    return 0;
//    }();
//class Solution {
//public:
//    vector<int> sortByBits(vector<int>& arr) {
//        ranges::sort(arr, [&](int x, int y) {
//            if (bit[x] < bit[y]) {
//                return true;
//            }
//            if (bit[x] > bit[y]) {
//                return false;
//            }
//            return x < y;
//            });
//        return arr;
//    }
//};

//461. 汉明距离

//两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
//给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

//class Solution {
//public:
//    int hammingDistance(int x, int y) {
//        return popcount(static_cast<uint32_t>(x ^ y));
//    }
//};

//2220. 转换数字的最少位翻转次数

//一次 位翻转 定义为将数字 x 二进制中的一个位进行 翻转 操作，即将 0 变成 1 ，或者将 1 变成 0 。
//比方说，x = 7 ，二进制表示为 111 ，我们可以选择任意一个位（包含没有显示的前导 0 ）并进行翻转。
//比方说我们可以翻转最右边一位得到 110 ，或者翻转右边起第二位得到 101 ，或者翻转右边起第五位（这一位是前导 0 ）得到 10111 等等。
//给你两个整数 start 和 goal ，请你返回将 start 转变成 goal 的 最少位翻转 次数。

//class Solution {
//public:
//    int minBitFlips(int start, int goal) {
//        return popcount(static_cast<uint32_t>(start ^ goal));
//    }
//};

//1342. 将数字变成 0 的操作次数

//给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。

//class Solution {
//public:
//    int numberOfSteps(int num) {
//        int step = 0;
//        while (num) {
//            step++;
//            if (num & 1) {
//                num ^= 1;
//            }
//            else {
//                num >>= 1;
//            }
//        }
//        return step;
//    }
//};

//476. 数字的补数

//对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。
//例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。
//给你一个整数 num ，输出它的补数。

//class Solution {
//public:
//    int findComplement(int num) {
//        int mask = (1ll << (int)log2(num) + 1) - 1;
//        return num ^ mask;
//    }
//};

//1009. 十进制整数的反码

//每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101"，11 可以用二进制 "1011" 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。
//二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。
//给你一个十进制数 N，请你返回其二进制表示的反码所对应的十进制整数。

//class Solution {
//public:
//    int bitwiseComplement(int n) {
//        if (n == 0) {
//            return 1;
//        }
//        int mask = (1ll << (int)log2(n) + 1) - 1;
//        return n ^ mask;
//    }
//};

//868. 二进制间距

//给定一个正整数 n，找到并返回 n 的二进制表示中两个 相邻 1 之间的 最长距离 。如果不存在两个相邻的 1，返回 0 。
//如果只有 0 将两个 1 分隔开（可能不存在 0 ），则认为这两个 1 彼此 相邻 。两个 1 之间的距离是它们的二进制表示中位置的绝对差。例如，"1001" 中的两个 1 的距离为 3 。

//class Solution {
//public:
//    int binaryGap(int n) {
//        int last = -1, ans = 0;
//        for (int i = 0; n; ++i) {
//            if (n & 1) {
//                if (last != -1) {
//                    ans = max(ans, i - last);
//                }
//                last = i;
//            }
//            n >>= 1;
//        }
//        return ans;
//    }
//};

//2917. 找出数组中的 K-or 值

//给你一个整数数组 nums 和一个整数 k 。让我们通过扩展标准的按位或来介绍 K - or 操作。
//在 K - or 操作中，如果在 nums 中，至少存在 k 个元素的第 i 位值为 1 ，那么 K - or 中的第 i 位的值是 1 。
//返回 nums 的 K - or 值。

//class Solution {
//public:
//    int findKOr(vector<int>& nums, int k) {
//        int ans = 0;
//        for (int i = 0; i < 31; i++) {
//            int cnt1 = 0;
//            for (int x : nums) {
//                cnt1 += x >> i & 1;
//            }
//            if (cnt1 >= k) {
//                ans |= 1 << i;
//            }
//        }
//        return ans;
//    }
//};

//693. 交替位二进制数

//给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

//class Solution {
//public:
//    bool hasAlternatingBits(int n) {
//        long x = n ^ (n >> 1);
//        return !(x & (x + 1));
//    }
//};

//2657. 找到两个数组的前缀公共数组

//给你两个下标从 0 开始长度为 n 的整数排列 A 和 B 。
//A 和 B 的 前缀公共数组 定义为数组 C ，其中 C[i] 是数组 A 和 B 到下标为 i 之前公共元素的数目。
//请你返回 A 和 B 的 前缀公共数组 。
//如果一个长度为 n 的数组包含 1 到 n 的元素恰好一次，我们称这个数组是一个长度为 n 的 排列 。

//class Solution {
//public:
//    vector<int> findThePrefixCommonArray(vector<int>& a, vector<int>& b) {
//        uint64_t p = 0, q = 0;
//        for (int i = 0; i < a.size(); i++) {
//            p |= 1ULL << a[i];
//            q |= 1ULL << b[i];
//            a[i] = popcount(p & q);
//        }
//        return a;
//    }
//};
//
//class Solution {
//public:
//    vector<int> findThePrefixCommonArray(vector<int>& a, vector<int>& b) {
//        const int n = a.size();
//        vector<int> ans(n);
//        bitset<51> set_a, set_b;
//
//        for (int i = 0; i < n; i++) {
//            set_a.set(a[i]);
//            set_b.set(b[i]);
//            ans[i] = (set_a & set_b).count();
//        }
//
//        return ans;
//    }
//};

//231. 2 的幂

//给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
//如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

//class Solution {
//public:
//    bool isPowerOfTwo(int n) {
//        return n > 0 && popcount(static_cast<uint32_t>(n)) == 1;
//    }
//};

//342. 4的幂

//给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
//整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x

//class Solution {
//public:
//    bool isPowerOfFour(int n) {
//        return n > 0 && popcount(static_cast<uint32_t>(n)) == 1 && n & 0x55555555;
//        //popcount(static_cast<uint32_t>(n)) == 1 == (n & (n - 1)) == 0
//    }
//};

//191. 位1的个数

//给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。

//class Solution {
//public:
//    int hammingWeight(uint32_t n) {
//        int ret = 0;
//        while (n) {
//            n &= n - 1;
//            ret++;
//        }
//        return ret;
//    }
//};

//338. 比特位计数

//给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

//class Solution {
//public:
//    vector<int> countBits(int n) {
//        vector<int> ans(n + 1);
//        int highbit = 0;
//        for (int i = 1; i <= n; i++) {
//            if ((i & (i - 1)) == 0) {
//                highbit = i;
//            }
//            ans[i] = ans[i - highbit] + 1;
//        }
//        return ans;
//    }
//};

//2595. 奇偶位数

//给你一个 正 整数 n 。
//用 even 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的偶数下标的个数。
//用 odd 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的奇数下标的个数。
//请注意，在数字的二进制表示中，位下标的顺序 从右到左。
//返回整数数组 answer ，其中 answer = [even, odd] 。

//class Solution {
//public:
//    vector<int> evenOddBit(int n) {
//        vector<int> ans(2);
//        for (int i = 0; n; n >>= 1) {
//            ans[i] += n & 1;
//            i ^= 1; // 切换奇偶
//        }
//        return ans;
//    }
//};

//2154. 将找到的值乘以 2

//给你一个整数数组 nums ，另给你一个整数 original ，这是需要在 nums 中搜索的第一个数字。
//接下来，你需要按下述步骤操作：
//如果在 nums 中找到 original ，将 original 乘以 2 ，得到新 original（即，令 original = 2 * original）。
//否则，停止这一过程。
//只要能在数组中找到新 original ，就对新 original 继续 重复 这一过程。
//返回 original 的 最终 值。

//class Solution {
//public:
//    int findFinalValue(vector<int>& nums, int original) {
//        int mask = 0;
//        for (int num : nums) {
//            if (num % original == 0) {
//                int k = num / original; // 倍数
//                if ((k & (k - 1)) == 0) { // 倍数是 2 的幂次
//                    mask |= k;
//                }
//            }
//        }
//        mask = ~mask; // 取反后，找最低位的 1（lowbit = mask & -mask）
//        return original * (mask & -mask);
//    }
//};

//3211. 生成不含相邻零的二进制字符串

//给你一个正整数 n。
//如果一个二进制字符串 x 的所有长度为 2 的子字符串中包含 至少 一个 "1"，则称 x 是一个 有效 字符串。
//返回所有长度为 n 的 有效 字符串，可以以任意顺序排列。

//class Solution {
//public:
//    vector<string> validStrings(int n) {
//        vector<string> ans;
//        int mask = (1 << n) - 1;
//        for (int x = 0; x < (1 << n); x++) {
//            if (((x >> 1) & x) == 0) {
//                ans.emplace_back(bitset<18>(x ^ mask).to_string().substr(18 - n));
//            }
//        }
//        return ans;
//    }
//};